In a control system a controller interacts periodically with a controlled object in the physical world in order to realize the desired behavior of the controlled object.
These periodic interactions between the controller and the controlled object occur at two different periodic instants: (i) the point of observation (or sampling instant) where the controller observes the state of the controlled object and (ii) the point of actuation (or actuation instant) where the controller sets set points of the actuators that act in the physical world in order to influence the future physical behavior of the controlled object.
In many cases the controller is realized by a distributed computer system consisting of node-computers with sensors, node-computers that execute a control model and node-computers that control actuators. The node-computers exchange messages using a real-time communication system.
The sequence of the computational and communication actions between a sampling instant and the corresponding actuation instant forms a frame. The duration of a frame should be constant in a given mode of operation. The end-point of a frame is the start-point of the succeeding frame.
In a time-triggered (TT) controller, where a preferably fault-tolerant global notion of a sparse time base is available at all node-computers, the periodic sampling instants, the periodic actuation instants and the periodic instants when messages are sent and received by the time-triggered communication system are specified during the development phase.
The sparse time base supports the system-wide consistent ordering of events in the temporal domain [1].
It follows that in a time-triggered (TT) controller the slot length for a computational action, i.e., the time interval between the start and the termination of the execution of the control model, is fixed and must be determined a priori during the development phase.
It is the objective of this invention to present a method for the determination of the slot lengths for the computational actions in a time-triggered controller.
This objective is achieved with a method with the features of claim 1.
Anytime Algorithms
The minimal slot length for the execution of the control algorithm in the control model must be long enough that for all data points of the input domain the control model can deliver a satisficing result.
A result is a satisficing result [2] if it is adequate (but not necessarily optimal) in the particular situation and meets all safety assertions.
The WCET (worst-case execution time) analysis of the control algorithm that delivers the satisficing result must be determined by using state-of-the art methods for WCET calculation [3].
The state-of-the art methods for WCET calculation of an algorithm bring about an over-dimensioned slot length because the WCET analysis has to fight two enemies, an enemy from below and an enemy from above. The enemy from below refers to temporal indeterminism that is inherent in modern hardware architectures. The enemy from above refers to algorithmic issues, e.g., the complexity of a computationally expensive algorithm that makes it hard to establish a tight WCET bound for all data points of the given input domain.
It follows that for the majority of data points of the input domain the control algorithm will deliver the satisficing result early and leave a substantial time interval between the termination of the control algorithm and the termination of the provided execution slot duration unused. We call this unused time interval the laxity of an execution slot.
In order to make productive use of the laxity the deployment of anytime algorithms is proposed in control systems [4].
An anytime algorithm consists of a core segment followed by an enhancing segment. The slot length for the execution of the anytime algorithm in the controller must be at least as long as the WCET of the core segment of the anytime algorithm. This minimal duration of the slot length for the computational control action is called the minimum execution slot duration. The execution of the core segment guarantees a satisficing result.
In an anytime algorithm, the satisficing result is iteratively improved by the enhancing segment until the endpoint of the provided execution slot, the deadline is reached. Iterative improvements of the satisficing result are achieved by the repeated execution of the enhancing segment until the deadline is reached. A good example for an anytime algorithm is Newton's method for finding successively better approximations for the roots of an equation.
The slot length for the execution of the anytime algorithm that ensures that the precision of the result of the anytime algorithm is better than a specified precision bound is called the maximum execution slot duration. The result that is delivered at the end of the maximum execution slot duration is called a precise result of the anytime algorithm.
If the provided slot length for the execution of the anytime algorithm is shorter than the maximum execution slot duration then the execution of the anytime algorithm will be interrupted (at the end of the provided slot length) before it can deliver a precise result. We call the result delivered by the anytime algorithm at the instant of interruption an imprecise result of the anytime algorithm.
We call the absolute value of the difference between the precise result of an anytime algorithm and an imprecise result of the anytime algorithm at the instant of interruption the anytime-algorithm impreciseness. The impreciseness of the anytime algorithm will increase, if the execution slot duration of the anytime algorithm is reduced.
Model Based Control
In a model-based control system, the controller contains an approximate model of the behavior of the controlled object (the control model) in its open environment. This control model is used for calculating the set points that are delivered to the actuators at the end of each frame.
The state-space of the control model encompasses four types of variables                Independent variables of the control system that are set by the operator. The values of these variables specify the objectives and constraints of the control system and are thus determined by an authority outside the control system.        Independent variables of the controlled object that are set by the controller (i.e. the controller outputs or setpoints for the actuators). The control model calculates new values of these variables during each frame.        Observable state variables—observable variables denoting the state of the controlled object and the state of the environment at the instant of observation. i.e. the start of a frame.        Hidden state variables that are part of the model in the controller. The hidden state variables are of eminent importance, since they carry the knowledge acquired in one frame to the following frame.        
At the instant beginning of a frame, let us say framek, of a periodic frame-based controller the observable state variables are observed by the controller. During a frame new values for the independent variables of the controlled object (the setpoints) and anticipated values of the observable and the hidden state variable are calculated by the control model for the instant end of framek (that is also the beginning of framek+1).
The difference between the anticipated value of an observable state at the end of framek and the observed value of this state variable at the end of framek, the model error, is an important input to the model for the calculations of the controller outputs in the following frame. After every frame the prediction horizon is shifted one frame further into the future. For this reason model-based control is sometimes called receding horizon control.
Model Error
The following simple example depicts an open system, the temperature control of the liquid in a reservoir for water purification. The temperature of the liquid in the reservoir can be raised by setting the actuator valve that controls the flow of hot water through a pipe system that is contained in the reservoir. Environmental dynamics, e.g., wind or rain, lower the temperature of the liquid. It is the objective of the control system to keep the variable temperature of the liquid in the reservoir at a preset value.
In the model of this control system, the single physical quantity temperature of the liquid is thus represented by three different variables:                tsk: the desired (but in some operational situations not achievable) value of the independent variable temperature submitted by the operator for the instant beginning of frame k.        tok: the value of the variable temperature observed at the instant beginning of frame k.        tpk: the anticipated value of the controlled variable temperature predicted by the model for the instant beginning of frame k (which is also the end of frame k−1).        
We call the differencemek=/tpk−tok/the model error mek at the instant beginning of frame k.
The model error is caused by two different phenomena:                (i) Reality has changed since the last instant of observation. The impact of unidentified or unanticipated processes in the environment (environmental dynamics) of an open system increases with the length of a frame (and the timeslots allocated to a computational action).        (ii) Imperfections of the model: The model is not a true image for the behavior of reality. For example, nonlinearities that exist in reality have not been properly modeled.        
The model error will increase if we move further away from the instant where the observable state variables of the system have been observed, i.e. if the execution slot duration of the anytime algorithm is increased.
It is impossible to design a model of an open system that will not exhibit a model error, since it is impossible to consider the myriad of phenomena that are present in the environment of an open system [5].
To summarize, the impreciseness of the anytime algorithm will be lowered, if the execution slot duration is increased, but the model error will be lowered if the execution slot duration of the anytime algorithm is reduced.